浅谈树状数组

一、啥是树状数组?

树状数组,是支持 O(logn)O(logn) 单点修改,O(logn)O(logn) 前缀和查询的数据结构。

先来看代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 5;
LL tre[N]; int n, m;
int lowbit(int x) {
    return x & (-x);
}
void add(int pos, LL val) {
    for (int i = pos; i <= n; i += lowbit(i)) {
        tre[i] += val;
    }
}
LL query(int pos) {
    LL ret = 0;
    for (int i = pos; i; i &= (i - 1)) {
        ret += tre[i];
    }
    return ret;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), add(i, x);
    for (int op, x, k; m--; ) {
        scanf("%d%d%d", &op, &x, &k);
        if (op == 1) add(x, (LL)k);
        else printf("%lld\n", query(k) - query(x - 1));
    }
    return 0;
}

二、树状数组的tre[i]含义是什么

举例:

ii treitre_i 长度
11 A1A_1 11
22 A1+A2A_1 + A_2 22
33 A3A_3 11
44 A1+A2+A3+A4A_1 + A_2 + A_3 + A_4 44
55 A5A_5 11
66 A5+A6A_5 + A_6 22
77 A7A_7 11
88 A1+A2+A3+A4+A5+A6+A7+A8A_1 + A_2 + A_3 + A_4 + A_5 + A_6 + A_7 + A_8 88

所以,treitre_i 表示从第 ii 位开始往前数 lowbit(x)\operatorname{lowbit}(x) 个数的和。

那么如果要求第 1771 \sim 77 的数的和,就需要 tre[(1001101)2]+tre[(1001100)2]+tre[(1001000)2]+tre[(1000000)2]tre[(1001101)_2] + tre[(1001100)_2] + tre[(1001000)_2] + tre[(1000000)_2]

用几张图来感性认知一下树状数组:

假如要更新 A21A_{21} ,则需要更新 tre[21],tre[22],tre[24],tre[32]tre[21], tre[22], tre[24], tre[32]

既然理解了,那就写代码吧!